package master;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author chenyw
 * @date 2022/8/21 10:08
 *
 * 重排链表
 */
public class M143reorderList {

    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode slow = head;
        ListNode fast = head.next;
        //快慢指针找中间节点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode p = slow.next;
        slow.next = null;
        head = dummyNode.next;

        //后半段开始逆序
        ListNode pre = null;
        while (p != null) {
            ListNode tmp = p.next;
            p.next = pre;
            pre = p;
            p = tmp;
        }


        //合并
        p = pre;
        pre = dummyNode;
        while (p != null) {
            pre.next = head;
            ListNode tmp = head.next;
            head.next = p;
            pre = p;
            p = p.next;
            head = tmp;
        }
        if (head != null) {
            pre.next = head;
        }
//        pre.next = null;

    }

}
